# 差分数组
# import sortedcontainers
# class MyCalendarThree(object):
#
#     def __init__(self):
#         self.s = sortedcontainers.SortedList()
#         self.e = sortedcontainers.SortedList()
#         self.length = 0
#
#
#     def book(self, start, end):
#         """
#         :type start: int
#         :type end: int
#         :rtype: int
#         """
#         self.length += 1
#         self.s.add(start)
#         self.e.add(end)
#         left_index = 0
#         right_index = 0
#         max_len = 0
#         while left_index < self.length and right_index < self.length:
#             if self.s[left_index] < self.e[right_index]:
#                 max_len = max(max_len, left_index - right_index + 1)
#                 left_index += 1
#             else:
#                 while self.s[left_index] >= self.e[right_index]:
#                     right_index += 1
#         return max_len

# 线段树
import collections


class MyCalendarThree(object):

    def __init__(self):
        self.tree = collections.defaultdict(int)
        self.lazy = collections.defaultdict(int)

    def update(self, start, end, l, r, node):
        if r < start or l > end:
            return 0
        if l >= start and r <= end:
            self.tree[node] += 1
            self.lazy[node] += 1
        mid = (l + r) // 2
        self.update(start, end, l, mid, 2 * node + 1)
        self.update(start, end, mid + 1, r, 2 * node + 2)
        self.tree[node] = self.lazy[node] + max(self.tree[2 * node + 1], self.tree[2 * node + 2])
        return self.tree[node]

    def book(self, start, end):
        return self.update(start, end - 1, 0, 10 ** 9 - 1, 0)
